/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function (heights) {
  const m = heights.length
  const n = heights[0].length
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]  // 表示上下左右四个方向
  let left = 0, right = 999999, ans = 0
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    const queue = [[0, 0]]  // bfs队列
    let visited = new Array(m * n).fill(0)  // 是否已经访问过
    visited[0] = 1  // 开始访问第一个数
    while (queue.length) {  // 队不空 
      const [x, y] = queue.shift()
      for (let i = 0; i < dirs.length; i++) {
        const nx = x + dirs[i][0]
        const ny = y + dirs[i][1]
        // 下标在范围内，且未访问过，且高度<x则入队
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx * n + ny] && Math.abs(heights[x][y] - heights[nx][ny]) <= mid) {
          queue.push([nx, ny])  // 入队
          visited[nx * n + ny] = 1  // 访问
        }
      }
    }
    if (visited[m * n - 1]) {  // 如果能到右下角结点，则查找左边区域
      ans = mid
      right = mid - 1
    } else {  // 如果不能，说明x太小，不满足条件，查找右边区域
      left = mid + 1
    }
  }
  return ans
}
/**
 * 想了半天发现不是动态规划
 * 1、图 并查集
 * 2、二分查找+bfs：
 *  是否存在一条从左上角到右下角的路径，其经过的所有边权不大于x？
 */
console.log(minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]])) // 1
console.log(minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]])) // 2
// console.log(minimumEffortPath([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]])) // 0
// console.log(minimumEffortPath([[4, 3, 4, 10, 5, 5, 9, 2], [10, 8, 2, 10, 9, 7, 5, 6], [5, 8, 10, 10, 10, 7, 4, 2], [5, 1, 3, 1, 1, 3, 1, 9], [6, 4, 10, 6, 10, 9, 4, 6]]))
